Exercici 5 (Tasca 3).
(pumping lemma)
Comprovar aritmètica bàsica no és regular
Demostreu que els llenguatges següents sobre l’alfabet \{0,1,\#\} no són regulars.
- \{u\#v \mid u,v\in \{0,1\}^*\ \land\ v\text{ és submot de }u\}
- \{u\#v \mid u,v\in \{0,1\}^*\ \land\ (|u|<|v|\lor |u|\in 2\mathbb N)\}
- \{u\#v \mid u,v\in \{0,1\}^*\ \land\ \mathtt{value}_2(u)=\mathtt{value}_2(v)\}
- \{u\#v \mid u,v\in \{0,1\}^*\ \land\ \mathtt{value}_2(u)=\mathtt{value}_2(v)+1\}
- \{u\#v\#z \mid u,v\in \{0,1\}^*\ \land\ \mathtt{value}_2(u)+\mathtt{value}_2(v)=\mathtt{value}_2(z)\}